import java.util.*;

/**
 * Created by jack on 18/4/1.
 */
public class Pathsum {
    private int sum;
    private int currentsum = 0;
    private List<List<Integer>> pathlists = new ArrayList<>();
    private Stack<Integer> stack = new Stack<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum){
        this.sum = sum;
        if(root == null){
            pathlists.add(new ArrayList<>());
            return pathlists;
        }
        attempt(root);
        return pathlists;
    }

    private void attempt(TreeNode node){
        stack.push(node.val);
        currentsum += node.val;
        if(currentsum == sum && node.left == null && node.right == null){
            List<Integer> lists = new ArrayList<>();
            for(Integer i : (List<Integer>)stack){
                lists.add(i);
            }

            pathlists.add(lists);
        }
        if(node.left != null){
            attempt(node.left);
        }
        if(node.right != null){
            attempt(node.right);
        }
        stack.pop();
        currentsum -= node.val;
    }
}
